// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包堆为实现
// 堆的任何类型提供堆操作。界面堆是一棵树，其属性是每个节点都是其子树中的
// 最小值节点。
// 
// 树中的最小元素是根，索引为0。
// 
// 堆是实现优先级队列的常用方法。要构建优先级
// 队列，请将优先级为（负）的堆接口实现为
// 对Less方法进行排序，因此Push会添加项，而Pop会从队列中删除优先级最高的
// 项。例如，
// 实现；文件示例_pq_测试。go有完整的来源。
// 
package heap

import "sort"

// 接口类型描述了
// 对于使用此包中的例程的类型的要求。
// 任何实现它的类型都可以用作
// 最小堆，具有以下不变量（在调用
// Init后建立，或者如果数据为空或已排序）：
// 
// ！h、 0<=i<h.Len（）和2*i+1<=j<=2*i+2和j<h.Len（）
// 
// 注意，这个接口中的推送和弹出是为了调用包堆的
// 实现。要从堆中添加和删除内容，请使用heap。推和堆。流行音乐
type Interface interface {
	sort.Interface
	Push(x any) // 将x作为元素Len（）添加
	Pop() any   // 删除并返回元素Len（）-1。
}

// Init建立此包中其他例程所需的堆不变量。
// Init对于堆不变量
// 是幂等的，并且可以在堆不变量无效时调用。
// 复杂性为O（n），其中n=h.Len（）。
func Init(h Interface) {
	// heapify 
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

// Push将元素x推到堆上。
// 复杂性为O（logn），其中n=h.Len（）。
func Push(h Interface, x any) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop从堆中移除并返回最小元素（根据Less）。
// 复杂性为O（logn），其中n=h.Len（）。
// Pop相当于Remove（h，0）。
func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

// Remove从堆中移除并返回索引i处的元素。
// 复杂性为O（logn），其中n=h.Len（）。
func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

// Fix在索引i处的元素更改其值后重新建立堆排序。
// 更改索引i处元素的值，然后调用Fix相当于，
// 但比调用Remove（h，i）然后推送新值便宜。
// 复杂性为O（logn），其中n=h.Len（）。
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // 父
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // int溢出后j1<0 
			break
		}
		j := j1 // 左子
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // /=2*i+2 
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}
